222C - Reducing Fractions - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
 
#define print(a) for(auto x:a)cout<<x<<" ";cout<<'\n';
#define debug(x) cout<<#x<<" "<<x<<endl
#define all(a) (a).begin(),(a).end()
#define sz(a) (int)(a.size())
#define int   long long int
#define endl '\n'
#define ar array
 
const int M = 1e9 + 7;
const int N = 2e7+10;

int lpf[N];
vector<int>pfs;

void sv(){
    for(int i=2;i<N; i++){
        if(!lpf[i]){lpf[i]=i;pfs.push_back(i);}
        for(int j=0;j<sz(pfs) && i*pfs[j]<N && pfs[j]<=lpf[i];j++){
            lpf[i*pfs[j]]=pfs[j];
        }
    }
}

void solve(){
map<int,int>mpa,mpb;
int n,m;cin>>n>>m;
vector<int>a(n),b(m);
for(int i=0;i<n;i++){
    int x;cin>>x;
    a[i]=x;
    while(x>1){
        mpa[lpf[x]]++;
        x/=lpf[x];
    }
}
for(int i=0;i<m;i++){
    int x;cin>>x;
    b[i]=x;
    while(x>1){
        mpb[lpf[x]]++;
        x/=lpf[x];
    }
}


for(auto &[x,y]:mpa){
    int mn=min(y,mpb[x]);
    y-=mn;
    mpb[x]-=mn;
}

for(int i=0;i<n;i++){
    int prod=1,x=a[i];
    while(x>1){
        if(mpa[lpf[x]]>0){
            prod*=lpf[x];
            mpa[lpf[x]]--;
        }
        x/=lpf[x];
    }
    a[i]=prod;
}
for(int i=0;i<m;i++){
    int prod=1,x=b[i];
    while(x>1){
        if(mpb[lpf[x]]>0){
            mpb[lpf[x]]--;
            prod*=lpf[x];
        }
        x/=lpf[x];
    }
    b[i]=prod;
}

cout<<n<<" "<<m<<endl;
print(a); print(b);


// vector<int>ansa,ansb,va,vb;

// int prod=1;

// for(auto [x,y]:mpa){
//     for(int j=0;j<y;j++){
//        va.push_back(x);
//     }
// }

// for(auto [x,y]:mpb){
//     for(int j=0;j<y;j++){
//         vb.push_back(x);
//     }
// }
// sort(all(va)); sort(all(vb));
// prod=1;

// for(int i=0,j=sz(va)-1;i<=j; ){
//     if(prod*va[i]<1e7)prod*=va[i],i++;
//     else if(prod*va[j]<1e7)prod*=va[j],j--;
//     else{
//         ansa.push_back(prod);
//         prod=va[j];j--;
//     }
// }
// if(prod>1)ansa.push_back(prod);
// prod=1;
// for(int i=0,j=sz(vb)-1;i<=j; ){
//      if(prod*vb[i]<1e7)prod*=vb[i],i++;
//     else if(prod*vb[j]<1e7)prod*=vb[j],j--;
//     else{
//         ansb.push_back(prod);
//         prod=vb[j];j--;
//     }
// }
// if(prod>1)ansb.push_back(prod);
// if(sz(ansa)==0)ansa.push_back(1);
// if(sz(ansb)==0)ansb.push_back(1);

// cout<<sz(ansa)<<" "<<sz(ansb)<<endl;
// print(ansa);
// print(ansb);




}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
sv();
int t=1;   //cin>>t;
while(t--)solve();
return 0;}